The Internet is a global network of interconnected computers and computers networks that use a variety of different operating systems or languages, including UNIX, DOS, Windows, Macintosh, and others. To enable communication among these various systems and languages, the Internet uses a language called TCP/IP (Transmission Control Protocol/Internet Protocol). TCP/IP supports three basic applications on the Internet: transmitting and receiving electronic mail, logging into remote computers (the Telnet), and transferring files and programs from one computer to another (FTP or File Transfer Protocol).
A primary design goal of TCP/IP is to interconnect networks that provide universal communication services, i.e., an “internetwork”, or “Internet”. Each physical network has its own technology dependent communication interface, in the form of a programming interface, which provides basic communication functions running between the physical network and the user applications. The architectures of the physical networks are hidden from the user. Another goal of TCP/IP is to interconnect different kinds of physical networks to form what appears to the user to be one large network.
The TCP/IP protocol suite is named for two of the most important protocols, namely Transmission Control Protocol (TCP), and Internet Protocol (IP). Another name for it is the Internet Protocol Suite. The more common term TCP/IP is used to refer to the entire protocol suite.
TCP is a transport layer protocol providing end-to-end data transfer. It is responsible for providing reliable exchange of information between two computer systems. Multiple applications can be supported simultaneously over a single TCP connection between two computer systems.
IP is an internetwork layer protocol hiding the physical network architecture below it. Messages exchanged between computers include a routing function that ensures that the messages will be correctly directed within the network to be delivered to their destinations. IP provides this routing function. An IP message may be called an IP Datagram.
Application Level protocols are used on top of TCP/IP to transfer user and application data from an origin computer system to a destination computer system. Such Application Level protocols are, for example, File Transfer Protocol (FTP), Telnet, Gopher, and Hyper Text Transfer Protocol (HTTP).
With the increasing size and complexity of the Internet, tools called navigators or navigation systems have been developed to help find information on the network. Early navigation systems include standards such as Archie, Gopher, and WAIS.
More recently, the navigation system widely known as the World Wide Web (“WWW” or “the Web”) has emerged. The Web is an Internet-based navigation system, an information distribution and management system for the Internet, and a dynamic format for communicating on the Web.
The Web seamlessly integrates information that has a wide variety of formats, including still images, text, audio, and video. A user of the Web with a graphical user interface (GUI) may communicate transparently with different host computers and different system applications (including FTP and Telnet), using different information formats for files and documents including, for example, text, sound and graphics.
A “Router” is a computer that interconnects two networks and forwards messages from one network to the other. Routers are able to select the best transmission path between networks. The basic routing function is implemented in the IP layer of the TCP/IP protocol stack, so any host (or computer) or workstation running TCP/IP over more than one interface could, in theory, forward messages between networks. Because IP implements the basic routing functions, the term “IP Router” is often used. However, dedicated network hardware devices called “routers” can provide more sophisticated routing functions than the minimum functions implemented in IP.
When data is sent to a remote destination, each IP datagram is first sent to a local router. An incoming datagram that specifies a destination IP address other than one of the local router IP address is treated as a normal outgoing datagram. This outgoing datagram is subject to the IP routing algorithm of the router, which selects the next hop for the datagram. The router forwards each datagram towards its final destination. A datagram travels from one router to another until it reaches a router connected to the destination. Each intermediate router along the end-to-end path selects the next hop used to reach the destination. The next hop represents the next router along the path to reach the destination. This next router can be located on any of the physical networks to which the intermediate router is attached. If it is a physical network other than the one on which the host originally received the datagram, then the result is that the intermediate router has forwarded the IP datagram from one physical network to another.
An IP routing table in each router is used to forward datagrams between networks. A basic IP routing table comprises information about the locally attached networks and the IP addresses of other routers located on these networks, plus the networks they attach to. A routing table can be extended with information on IP networks that are farther away, and can also comprise a default route, but it still remains a table with limited information. A routing table represents only a part of the whole IP network. A router having such a routing table is called “a router with partial routing information.”
A robust routing protocol must provide the ability to dynamically build and manage information in the IP routing table. As changes in the network topology may occur, the routing tables must be updated with minimal intervention, and preferably without manual intervention.
IP addresses are used by the IP protocol to uniquely identify a host on the Internet. Strictly speaking, an IP address identifies an interface that is capable of sending and receiving IP datagrams. Each IP datagram (the basic data packets that are exchanged between hosts) comprises a source IP address and a destination IP address. An IP address may be represented by a 32-bit unsigned binary value expressed in a dotted decimal format. For example, 9.167.5.8 is a valid Internet address. Such an IP address is divided between a network part and a host part. The first bits of the IP address specify how the rest of the address is divided. The mapping between the IP address and an easier-to-read symbolic name, for example myhost.ibm.com, is done by the “Domain Name System” (DNS).
An IP address comprises a list four numbers in the range 0 to 255 separated by periods. All possible addresses in the IP network (in other words, the entire IP address space) are between address 0.0.0.0 and address 255.255.255.255. The total number of available IP addresses is 2 raised to the power 32. An IP address can also be represented by converting each digit to a binary value. For example, the IP address “0.1.2.3” can be represented by the binary value “00000000 00000001 00000010 00000011”.
An address which results from adding 1 to the binary representation of a first address is considered to be “contiguous” to the first address. The total address space can be split into smaller blocks of contiguous addresses using a binary mask. These blocks of contiguous addresses are called “subnetworks” or “subnets.” A subnet is defined by two values: the size of the mask to apply (a number “n” between 0 and 32), and the first address of the block (which must be a multiple of 2 to the power (32−n)). Once these two values are given, it is easy to check whether an address “x” belongs to this subnet by applying the binary mask to the binary representation of the IP address “x”. The result must be equal to the first address of the subnet. The mask is applied to an address by means of a logical “AND” operation between the bits of the mask and the corresponding bits of the address in question. As the mask is a characteristic of the subnet, it is usually called the “subnet mask”. The subnet mask is entirely defined by its length “n” currently denoted “/n”.
For instance, the subnet defined by the subnet mask /30 and the address 1.1.1.0 has the block of contiguous addresses between 1.1.1.0 and 1.1.1.3, with the four addresses 1.1.1.0, 1.1.1.1, 1.1.1.2, and 1.1.1.3. In other words, mask /30 can be represented by the binary string “11111111 11111111 11111111 11111100”. An address belongs to the subnet previously defined if, when the binary mask /30 is applied to the binary representation of the address, the result is equal to the first address of the subnet, in the present case “00000001 00000001 00000001 00000000”. For example, if the mask /30 is applied to the address “1.1.1.2” represented by the string “00000001 00000001 00000001 00000010”, the result is equal to “00000001 00000001 00000001 00000000” which is the first address of the subnet. Therefore the address “1.1.1.2” belongs to the subnet. On the contrary, if the same operation is done on address “2.2.2.2” represented by the binary string “00000010 00000010 00000010 00000010”, the result is “00000010 00000010 00000010 00000000”. The result is different from the first address of the subnet. Therefore, address “2.2.2.2” does not belong to the subnet.
More-intelligent routers are required if the router needs to know routes to all possible IP networks; if the router needs to have dynamic routing tables, which are kept up-to-date with minimal or no manual intervention; and if the router must be able to advertise local changes to other routers.
Advanced forms of routers use additional protocols to communicate with each other. A number of protocols of this kind exist. For instance, a group of networks, called an “Autonomous System” (AS) in Internet terminology, is administered as a unit. Routing within an Autonomous System (AS) and routing outside an Autonomous System (AS) are treated as different issues and are addressed by different protocols.
An Autonomous System (AS) is defined as a logical portion of a larger IP network. An AS normally comprises an internetwork within an organization. It is administered by a single management authority. An AS can connect to another AS managed by the same organisation. It can also connect to other public or private networks.
Some routing protocols are used to determine the routing path within an AS, and others are used between a plurality of Autonomous Systems. Exterior Gateway Protocols (EGPs) allow the exchange of summary information between separately administered Autonomic Systems. An example of this type of routing protocol is the Border Gateway Protocol (BGP), which is also called EBGP for Exterior Border Gateway Protocol. Interior Gateway Protocols (IGPs) allow routers to exchange information within an AS. Examples of these protocols are Open Short Path First (OSPF) and Routing Information Protocol (RIP). The routing protocol BGP can also be used within an AS as IGPs. In this particular case, BGP is called Internal Border Gateway Protocol (IBGP).
The Exterior Gateway Protocol (EGP) has particular historical interest. It was one of the first protocols developed to communicate between Autonomous Systems. This protocol is described in RFC 904. EGP assumes that the network comprises a single backbone, and that a single path exists between any two Autonomous Systems. Due to this limitation, the current use of EGP is minimal. In practice, EGP has been replaced progressively by BGP. EGP is based on periodic polling using hello/I-hear-you message exchanges, to monitor neighbor reachability and poll requests to solicit update responses. Exterior gateways connected to an AS can advertise only those destinations networks reachable entirely within that gateway's AS. An exterior gateway using EGP passes along information to its EGP neighbors but does not advertise reachability information about its EBGP neighbors (gateways are neighbors if they exchange routing information) outside the AS. The routing information from inside an AS must be collected by this EGP gateway, usually via an Interior Gateway Protocol (IGP).
Border Gateway Protocol (BGP) is an Exterior Gateway Protocol. It was originally developed to provide a loop-free method for exchanging routing information between Autonomous Systems. BGP has since evolved to support the aggregation and summary of routing information. BGP is an IETF draft standard protocol described in RFC 1771. The version described in this RFC is BGP version 4 (BGP-4).
A system running the Border Gateway Protocol (BGP) is called a “BGP speaker.” BGP speakers exchanging inter AS routing information are called “BGP neighbors.” BGP neighbors can be of two types:                Internal: a pair of BGP neighbors in the same Autonomous System. Internal BGP neighbors must present a consistent image of the AS.        External: a pair of BGP neighbors in different Autonomous Systems. External BGP neighbors must be connected by a BGP connection.        
A “BGP session” is a TCP session established between BGP neighbors exchanging routing information using BGP. The neighbors monitor the state of the session by sending a “keep-alive” message regularly.
A “border router” or “border gateway” is a router that has a connection to multiple Autonomous Systems. The IP address of a border router is specified as a next hop destination when BGP advertises an AS path (list of the AS numbers traversed by a route when exchanging routing information) to one of its external neighbors. Next hop border routers share a physical connection with both the sending and receiving BGP speakers.
BGP defines two types of connections, physical connections and BGP connections.
In a physical connection, an AS shares a physical network with another AS, and this network is connected to at least one border router from each AS. Since these two routers share a network, they can forward datagrams to each other without requiring any inter-AS or intra-AS routing protocols.
In a BGP connection, there is a BGP session between a pair of BGP speakers, one in each AS. This session is used to communicate the routes through the physically connected border routers that can be used for specific networks. BGP requires that the BGP speakers must be on the same network as the physically connected border routers so that the BGP session is also independent of all inter-AS or intra-AS routing protocols. The BGP speakers do not need to be border routers, and vice versa. The term BGP connection can be used to refer to a session between two BGP speakers in the same AS.
Routing policies are not defined in the BGP protocol. Rather, they are selected by the AS authority and presented to BGP in the form of implementation specific configuration data. Each BGP speaker must evaluate different paths to a destination from the border routers for an AS connection, select the best one that complies with the routing policies in force, and advertise that route to all of its BGP neighbors at that AS connection. Rather than exchange simple metric counts, BGP communicates entire paths to its neighbors. BGP determines a preference order by applying a function mapping each path to a preference value and selects the path with the highest value.
BGP advertises only routes that it uses itself to its neighbors. That is, BGP conforms to the normal Internet hop-by-hop paradigm, even through it has additional information in the form of AS paths and is theoretically capable of informing a neighbor of a route it would not use itself. When two BGP speakers form a BGP session, they begin by exchanging their entire routing tables. Routing information is exchanged via “update” messages. In addition to the reachability and next hop information, the routing information contains the complete AS path to each listed destination in the form of a list of AS numbers. After BGP neighbors have performed their initial exchange of their complete routing databases, they exchange only updates to that information.
The Border Gateway Protocol (BGP) is used by BGP routers to route datagrams in the Internet Protocol (IP) network. According to this protocol, the various BGP routers exchange routing tables. Each router adds the routes it learns from its BGP neighbors to the routes stored in its own routing table, and then propagates this table to its neighbors. The routes are transmitted from one router to another. Consequently, the size of the routing table of each router can rapidly become very large. At the end, the routing table can contain all routes known by every router participating in the Border Gateway Protocol (BGP) on the Internet; this table is called “the full Internet table”.
With the rapid expansion of Internet, the size of the “full Internet table” has grown very rapidly. As a result, the size of the memory required to store such a table in a router and the data processing capacity required to manage it can present a significant problem. The technical literature has discussed the problem raised by this expansion. For example, see “Faster 'Net growth rate raises fears about routers” by Carolyn Duffy Marsan in Network World, Apr. 2, 2001 (http://www.nwfusion.com/news/2001/0402routing.html), which indicates that the Internet is growing in size and complexity at a rate faster than today's routers can handle. After years of predictable growth, the size of the routing table and traffic is exploding.
To cope with the size increase of routing tables, manufacturers have continuously increased the power available in their routers in terms of memory for storing the tables, and in terms of data processing for consulting and updating the tables. In fact, network designers must either develop more powerful (and more expensive) routers in proportion to the size of the routing tables, or find a way to artificially limit or decrease the size of the routing tables. In the latter case, the usual technique is to implement a filter and to discard some of the table entries, typically entries related to small networks. However, this loss of information has its own drawbacks, especially if the routing that results is no longer optimal.
As table size increases, some of the routers within a network may abruptly reach their limits. Suddenly, networks that were operating properly encounter problems related to the capacity of routers to route the traffic. When this happens, one solution is to replace old routers with new routers that are more powerful. Another solution is to deliberately reduce the size of the full Internet table by discarding some routes and by filtering, as mentioned above.